import test0ne.TreeNode;

import java.util.*;

public class Test {

    private static long timeToLong(String str) {
        String[] strs = str.split(":");
        return Long.parseLong(strs[0])*3600 + Long.parseLong(strs[1])*60 + Long.parseLong(strs[2]);
    }

    private static int f(int a, int b) {
        int c;
        do {
            c = a ^ b;
            b = a & b << 1;
            a = c;
        }while (b!= 0);

        return c;

    }

    public static int maxArea(int[] height) {
        int max = 0;
        int left = 0, right = height.length-1;
        while (left<right) {
            if(height[left] < height[right]) {
                max = Math.max(max, height[left]* (right-left));
                left++;
            }else {
                max = Math.max(max, height[right]* (right-left));
                right--;
            }
        }
        return max;
    }

    private static int strStr(String haystack, String needle) {
        if(haystack.equals("") && needle.equals("")) {
            return 0;
        }

        char[] left = haystack.toCharArray();
        char[] right = needle.toCharArray();
        for (int i = 0; i < left.length; i++) {
            if((left.length - i )<right.length) {
                return -1;
            }
            int l = i;
            int r = 0;
            boolean flag = true;
            while (l<left.length && r<right.length) {
                if(left[l++] != right[r++]) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                return i;
            }
        }
        return -1;
    }

    private static void each(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();

        if(root!=null) {
            q.add(root);
        }

        while (!q.isEmpty()) {
            TreeNode r = q.poll();
            System.out.println(r.val);

            if(r.left != null) {
                q.add(r.left);
            }
            if(r.right != null) {
                q.add(r.right);
            }
        }
    }


    private static String sqrt() {
        Double x = 1.414;
        while (x.toString().length()<12) {
            int low = 0;
            int high = 9;
            int mid = (low + high) / 2;
            Double one =  getNextHarf(x, mid);

            Double result = one * one;
            if( result<2 ) {
                while ( one * one <2 && mid<=8) {
                    one = getNextHarf(x, ++mid);
                }
                x = getNextHarf(x, --mid);
            }else {
                while ( one * one >2 && mid>=1) {
                    one = getNextHarf(x, --mid);
                }
                x = one;
            }



        }
        return x.toString();
    }

    private static double sqrt2() {
        double low =1.4;
        double high =1.5;


        while ((high-low) > 0.0000000001) {
            double mid = (low+high)/2;
            if(mid*mid>2) {
                high = mid;
            }else {
                low = mid;
            }
        }
        return low;
    }

    private static double getNextHarf(Double x, Integer o) {
        return Double.parseDouble(x.toString()+o);
    }

    public static int removeDuplicates(int[] nums) {
        int slow = 0;
        int quick = 0;
        while (quick<nums.length) {
            int pre = nums[slow];
            if(nums[quick] != pre) {
                slow++;
                nums[slow] = nums[quick];
            }
            quick++;
        }
        return slow+1;
    }

//    public static int search(int[] nums, int target) {
//        int l = 0;
//        int r = nums.length-1;
//        while (l<r) {
//            if()
//
//        }
//        return -1;
//    }

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        permutation(nums, 0, result);
        return result;
    }

    private static void permutation(int[] nums, int i, List<List<Integer>> result) {
        if(i==nums.length) {
            List<Integer> list = new LinkedList<>();
            for (int num : nums) {
                list.add(num);
            }
            result.add(list);
        }else {
            for (int j = i; j < nums.length; j++) {
                swap(nums, i, j);
                permutation(nums, i+1, result);
                swap(nums, i, j);
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        System.out.println(permute(new int[]{1,2,3}));
    }
}
